package ans.p18;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * #      18
 * 名称   四数之和
 * 链接   https://leetcode-cn.com/problems/4sum
 * 题解   [1104](https://leetcode-cn.com/problems/4sum/solution)
 * 通过率 40.1%
 * 难道   中等
 */
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        return nSum(nums, target, 4);
    }


    /*
     **  n数之和
     **  @param number 要求几个数
     */
    public static List<List<Integer>> nSum(int[] nums, int target, int number) {
        if (nums.length < number) return new ArrayList<>();
        List<List<Integer>> result = new ArrayList<>();

        if (number > 2) {
            // number大于2时，继续划分和递归，直到 number == 2
            for (int i = 0; i < nums.length; i++) {
                // 递归，数组划分、目标值target更新、number减一
                List<List<Integer>> deeperResult = nSum(Arrays.copyOfRange(nums, i + 1, nums.length), target - nums[i], number - 1);
                // 收集下层递归的返回值并处理
                if (deeperResult.size() > 0) {
                    for (List<Integer> tempResult : deeperResult) {
                        tempResult.add(nums[i]);
                        // 去重后添加到result
                        if (!result.contains(tempResult)) {
                            result.add(tempResult);
                        }
                    }
                }
            }
        } else {
            // number == 2 时变为两数之和
            int i = 0, j = nums.length - 1;
            while (i < j) {
                if (nums[i] + nums[j] < target) {
                    i++;
                } else if (nums[i] + nums[j] > target) {
                    j--;
                } else {
                    List<Integer> tempResult = new ArrayList<>(Arrays.asList(nums[i], nums[j]));
                    if (!result.contains(tempResult)) {
                        result.add(tempResult);
                    }
                    i++;
                    j--;
                }
            }
        }

        return result;
    }

}
